class Solution {
private:
    vector<int> cache; // 用于存储已经计算过的子问题的结果

    // 递归函数：计算爬到第 i 个台阶的方法数
    int dfs(int i) {
        if (i <= 1) { // 递归的边界条件：若台阶数为0或1，只有1种方法
            return 1;
        }
        
        int &res = cache[i]; // 获取第 i 个台阶的结果引用
        if (res) { // 如果已经计算过，则直接返回结果
            return res;
        }

        // 记忆化递归：计算到第 i 个台阶的结果，递归调用分别计算 i-1 和 i-2 台阶的方法数
        return res = dfs(i - 1) + dfs(i - 2); // 记忆化：存储结果以避免重复计算
    }

public:
    int climbStairs(int n) {
        cache.resize(n + 1); // 初始化缓存大小，确保能存储到 n
        return dfs(n); // 从第 n 个台阶开始计算
    }
};